package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class _84_LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new _84_LargestRectangleInHistogram().new Solution();
        int[] heights = new int[]{2, 1, 5, 6, 2, 3};
        int i = solution.largestRectangleArea(heights);
        System.out.println(i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int largestRectangleArea(int[] heights) {
            int res = 0;
            Deque<Integer> stack = new LinkedList<>();
            int[] newHeights = new int[heights.length + 2];
            for (int i = 0; i < heights.length; i++) {
                newHeights[i + 1] = heights[i];
            }

            for (int i = 0; i < newHeights.length; i++) {
                while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                    int cur = stack.peek();
                    stack.pop();
                    int left = stack.peek();
                    int right = i;
                    res = Math.max(res, (right - left - 1) * newHeights[cur]);
                }
                stack.push(i);
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}